package leetcode_900;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *@author 周杨
 *PossibleBipartition_886_ 给定一些人互相讨厌的对象 最后问能否把这些人分配到两个不同的组里
 *describe:用并查集 AC 98%
 *2018年11月10日 下午9:24:36
 */
public class PossibleBipartition_886_ {
	
	/**
	 * describe:用dfs解决
	 * 2018年11月10日 下午9:24:07
	 */
	public boolean possibleBipartition2(int N, int[][] dislikes) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for(int i=0;i<N;i++){
            map.put(i, new HashSet<>());
        }
        for(int[] ele:dislikes){
            map.get(ele[0]-1).add(ele[1]-1);
            map.get(ele[1]-1).add(ele[0]-1);
        }
        
        boolean[] checked = new boolean[N];
        int[] colors = new int[N];
        Arrays.fill(colors, -1);
        for(int i=0;i<N;i++){
            if(checked[i] == true){
                continue;
            }
            colors[i] = 1;
            if(!colorGraph(colors, checked, map, i)){
                return false;
            }
        }
        return true;
    }
    
    public boolean colorGraph(int[] colors, boolean[] checked, Map<Integer,Set<Integer>> map, int cur_index){
         if(checked[cur_index]){
             return true;
         }
         checked[cur_index] = true;
         Set<Integer> neigbors = map.get(cur_index);
         for(int neig:neigbors){
               if(colors[neig] == -1){
                   colors[neig] = (colors[cur_index]==1)?2:1;
                   if(!colorGraph(colors,checked,map,neig)){
                       return false;
                   }
               }else if(colors[neig] == colors[cur_index]){
                    return false;
               }
         }
         
         return true;
    }
	
	
	 /**
	 * describe:用并查集
	 * 2018年11月10日 下午9:24:21
	 */
	public boolean possibleBipartition(int N, int[][] dislikes) {
	        int[] colors = new int[N + 1];
	        for(int i = 1; i <= N; ++i) colors[i] = i;
	        for(int i = 0; i < dislikes.length; ++i) {
	            int p1 = dislikes[i][0], p2 = dislikes[i][1];
	            if(colors[p2] == p2) colors[p2] = p1;
	            else {
	                int[] uf1 = find(p1, colors), uf2 = find(p2, colors);
	                if(uf1[0] == uf2[0] && uf1[1] == uf2[1]) return false;
	            }
	        }
	        return true;
	    }
	    
	    private int[] find(int p, int[] colors) {
	        int color = 0;
	        while(colors[p] != p) {
	            p = colors[p];
	            color = color == 0 ? 1 : 0;
	        }
	        return new int[] {p, color};
	    }
	/**
	 * describe:贪心算法 不知道哪里出错
	 * 2018年11月10日 下午6:45:44
	 */
	public boolean possibleBipartition1(int N, int[][] dislikes) {
        Arrays.sort(dislikes,(o1,o2)->o1[0]-o2[0]==0?o1[1]-o2[1]:o1[0]-o2[0]);//按第一个元素排序
        int[] seat=new int[N+1];//1表示分到1组 2表示分到2组
        for(int[] now:dislikes) {
        	if(seat[now[0]]==0&&seat[now[1]]==0) {//两者都没有分组
        		seat[now[0]]=1;
        		seat[now[1]]=2;
        	}
        	else {
        		if(seat[now[0]]!=0) {//已经给now[0]分配了组
        			if(seat[now[1]]!=0) {//now[1]也有组
        				if(seat[now[0]]==seat[now[1]]) return false;
        				else continue;
        			}
        			else {//now[1]没有组
        				if(seat[now[0]]==1)
        					seat[now[1]]=2;
        				else
        					seat[now[1]]=1;
        			}
        		}
        		else {//now[0]没有分组 那么now[1]分组了
        			seat[now[0]]=seat[now[1]]==1?2:1;
        		}
        	}
        }
        return true;
    }
}
